1735D - Meta-set - CodeForces Solution

bitmasks brute force data structures hashing math

Please click on ads to support us..

Python Code: 

from sys import stdin
input = stdin.readline

inp = lambda : list(map(int,input().split()))



def answer():

    ans = 0
    count , value = dict() , dict()
    
    for i in range(n):
        
        for j in range(i + 1 , n):

            need = []
            for x in range(k):
                if(a[i][x] == a[j][x]):
                    need.append(a[i][x])
                else:
                    need.append(3 - a[i][x] - a[j][x])


            need = tuple(need)
            if(need not in count):continue
            
            key = tuple(a[i])
            value[key] = value.get(key , 0) + count.get(need , 0)

            key = tuple(a[j])
            value[key] = value.get(key , 0) + count.get(need , 0)

            value[need] = value.get(need , 0) + count.get(need , 0)
            

        count[tuple(a[i])] = count.get(tuple(a[i]) , 0) + 1


    ans = 0
    for i in value.keys():
        ans += (value[i] * (value[i] - 1)) // 2

    return ans

for T in range(1):

    n , k = inp()
    a = [inp() for i in range(n)]

    print(answer())

C++ Code: 

#include <bits/stdc++.h>
#include <algorithm> 
// // pbds
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// // pbds

using namespace std;
// using namespace __gnu_pbds;

typedef long long ll;
typedef pair <ll,ll> pll;
// // pbds decl
// typedef tree <ll,null_type,less <ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// // pbds decl

void solve(){
	ll n,k;
	cin >> n >> k;

	vector <vector <ll>> v(n,vector <ll> (k,0));

	for(auto &e : v){
		for(auto &a : e){
			cin >> a;
		}
	} 

	map <vector <ll>,vector <pll>> freq;
	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			vector <ll> temp;

			for(int a=0;a<k;++a){
				temp.push_back((6 - (v[i][a] + v[j][a]))%3);
			}

			freq[temp].push_back({i,j});
		}
	}

	ll ans = 0;
	for(int i=0;i<n;++i){

		ll valid_pairs = 0;
		for(auto &e : freq[v[i]]){
			if(e.first != i && e.second != i){
				++valid_pairs;
			}
		}

		ans += valid_pairs * (valid_pairs - 1)/2;
	}

	cout << ans << "\n";

}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t = 1;
	while(t--){
		solve();
	}

	return 0;
}


Comments

Submit
0 Comments
More Questions

429. N-ary Tree Level Order Traversal
739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST
445. Add Two Numbers II
442. Find All Duplicates in an Array
437. Path Sum III
436. Find Right Interval
435. Non-overlapping Intervals
406. Queue Reconstruction by Height
380. Insert Delete GetRandom O(1)
332. Reconstruct Itinerary
368. Largest Divisible Subset
377. Combination Sum IV
322. Coin Change
307. Range Sum Query - Mutable
287. Find the Duplicate Number
279. Perfect Squares
275. H-Index II
274. H-Index
260. Single Number III
240. Search a 2D Matrix II
238. Product of Array Except Self
229. Majority Element II
222. Count Complete Tree Nodes
215. Kth Largest Element in an Array